PRA7: The Meeting! // Advanced

The programming club members, lost in the jungle of HHS, are desperately searching for a way to the programming club meeting (probably in A211). They start at (0,0) and must reach (n,n) the meeting location. The grid has size n X n. List the total number of possible paths which the programmers can take to reach the meeting (grid given in input).

Input Format

The dimensions of the grid are given first. From there, the grid is given in 0's and 1's. A 0 indicates that square is can be traversed by the programmers while a 1 indicates the square is blocked off.

Sample Input

3
0 0 0
0 1 0
0 0 0

Output Format

The number of total possible paths which the programmers can take to reach the meeting (without revisiting squares in a single path). In other words, the number of paths from (0,0) to (n,n).

Sample Output

2